class Solution {
    /**
     * 思路：遍历数组，同时记录下0到当前位置i的前缀和sum；同时用map记录每个位置的前缀和；
     * 对于当前位置i，我们可以要求以i结尾的构成和为k的序列，只需要直到map[ sum-k ]的个数即可
     *
     * map：key表示和，value表示个数
     */
    public int subarraySum(int[] nums, int k) {
        int nowSum = 0;
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        for (int i : nums){
            nowSum += i;
            if( map.get(nowSum-k)!=null ){
                res += map.get(nowSum-k);
            }
            // 记录前缀和
            map.put(nowSum, map.containsKey(nowSum) ? (map.get(nowSum)+1) : 1);
        }
        return res;
    }
}